perm filename CNTOUR[0,BGB]2 blob
sn#101475 filedate 1974-05-14 generic text, type C, neo UTF8
COMMENT ā VALID 00007 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 Video Image Contouring.
C00005 00003 THRESHOLDING.
C00009 00004 CONTOURING.
C00016 00005 NESTING.
C00022 00006 NESTING.
C00025 00007 CONTOUR SEGMENTION
C00047 ENDMK
Cā;
Video Image Contouring.
CRE consists of five steps: thresholding, contouring,
nesting, smoothing and comparing. Thresholding, contouring and
smoothing perform conversions between two different kinds of images.
Nesting and contouring compute topological relationships within a
given image representation. In summary the major operations are:
MAJOR OPERATION. OPERAND. RESULT.
1. THRESHOLDING: 6-BIT-IMAGE, 1-BIT-IMAGES.
2. CONTOURING: 1-BIT-IMAGES, VIC-IMAGE.
3. NESTING: VIC-IMAGE, NESTED-VIC-IMAGE.
4. SMOOTHING: VIC-IMAGE, ARC-IMAGE.
5. COMPARING: IMAGE & FILM, FILM.
Although the natural order of operations is sequential from
image thresholding to image comparing; in order to keep memory size
down, the first four steps are applied one intensity level at a time
from the darkest cut to the lightest cut (only nesting depends on
this sequential cut order); and comparing is applied to whole
images.
The illustrations on pages 21 and 23 show an initial video
image and its final smoothed contour image; the illustrations
immediately below and on page 24 the corresponding intermediate
sawtoothed contour images. The illustrated images are each composed
of seven intensity levels, and took 16 seconds and 13 seconds to
compute respectively (on a PDP-10, 2usec memory). The final CRE
data structures contained 680 and 293 nodes respectives, which comes
to 2K and 4.5K words respectively; the initial video image requires
10.2K words.
FIGURE: PUMP SAW TOOTHED CONTOURS.
~I1973,800;F8- 22 -
THRESHOLDING.
Thresholding, the first and easiest step, consists of two
subroutines, called THRESH and PACXOR. THRESH converts a 6-bit
image into a 1-bit image with respect to a given threshold cut level
between zero for black and sixty-three for light. All pixels equal
to or greater than the cut, map into a one; all the pixels less than
the cut, map into zero. The resulting 1-bit image is stored in a bit
array of 216 rows by 288 columns (1728 words) called the PAC
(picture accumulator) which was named in memory of McCormick's
ILLIAC-III. After THRESH, the PAC contains blobs of bits. A blob
is defined as "rook's move" simply connected; that is every bit of a
blob can be reached by horizontal or vertical moves from any other
bit without having to cross a zero bit or having to make a diagonal
(bishop's) move. Blobs may of course have holes. Or equalvalently
a blob always has one outer perimeter polygon, and may have one,
several or no inner perimeter polygons. This blob and hole topology
is recoverible from the CRE data structure and is built by the
nesting step.
Next, PACXOR copies the PAC into two slightly larger bit
arrays named HSEG and VSEG. Then the PAC is shifted down one row and
exclusive OR'ed into the HSEG array; and the PAC is shifted right
one column and exclusive OR'ed into the VSEG array to compute the
horizontal and vertical border bits of the PAC blobs. Notice, that
this is the very heart of the "edge finder" of CRE. Namely, PACXOR
is the mechanism that converts regions into edges.
~I1973,800;F8- 24 -
CONTOURING.
Contouring, converts the bit arrays HSEG and VSEG into
vectors and polygons. The contouring itself, is done by a single
subroutine named MKPGON, make polygon. When MKPGON is called, it
looks for the upper most left non-zero bit in the VSEG array. If the
VSEG array is empty, MKPGON returns a NIL. However, when the bit is
found, MKPGON traces and erases the polygonal outline to which that
bit belongs and returns a polygon node with a ring of vectors.
To belabor the details (for the sake of later complexities);
the MKGON trace can go in four directions: north and south along
vertical columns of bits in the VSEG array, or east and west along
horizontal rows of the HSEG array. The trace starts by heading south
until it hits a turn; when heading south MKPGON must check for first
a turn to the east (indicated by a bit in HSEG); next for no turn
(continue south); and last for a turn to the west. When a turn is
encountered MKPGON creates a vector node representing the run of
bits between the previous turn and the present turn. The trace
always ends heading west bound. The outline so traced can be either
the edge of a blob or a hole, the two cases are distinguished by
looking at the VIC-polygon's uppermost left pixel in the PAC bit
array.
There are two complexities: contrast accumulation and
dekinking. The contrast of a vector is defined as (QUOTIENT
(DIFFERENCE (Sum of pixel values on one side of the vector)(Sum of
pixel values on the other side of the vector)) (length of the vector
in pixels)). Since vectors are always either horizontal or vertical
and are construed as being on the cracks between pixels; the
specified summations refer to the pixels immediately to either side
of the vector. Notice that this definition of constrast will always
give a positive constrast for vectors of a blob and negative
contrast for the vectors of a hole.
The terms "jaggies", "kinks" and "sawtooth" all are used to
express what seems to be wrong about the lowermost left polygon on
page 25. The problem involves doing something to a rectilinear
quantized set of segments, to make its linear nature more evident.
The CRE jaggies solution (in the subroutine MKPGON) merely positions
the turning locus diagonally off its grid point alittle in the
direction (northeast, northwest, southwest or southeast) that
bisects the turn's right angle. The distance of dekink vernier
positioning is always less than half a pixel; but greater for
brighter cuts and less for the darker cuts; in order to preserve the
nesting of contours. The saw toothed and the dekinked versions of a
polygon have the same number of vectors. I am very fond of this
dekinking algorithm because of its incredible efficiency; given that
you have a north, south, east, west polygon trace routine (which
handles image coordinates packed row, column into one accumulator
word); then dekinking requires only one more ADD instruction
execution per vector !
NESTING.
The nesting problem is to decide whether one contour polygon
is within another. Although easy in the two polygon case; solving
the nesting of many polygons with respect to each other becomes
n-squared expensive in either compute time or in memory space. The
nesting solution in CRE sacrifices memory for the sake of greater
speed and requires a 31K array, called the SKY.
CRE's accumulation of a properly nested tree of polygons
depends on the order of threshold cutting going from dark to light.
For each polygon there are two nesting steps: first, the polygon is
placed in the tree of nested polygons by the subroutine INTREE;
second, the polygon is placed in the SKY array by the subroutine
named INSKY.
The SKY array is 216 rows of 289 columns of 18-bit pointers.
The name "SKY" came about because, the array use to represent the
furthest away regions or background, which in the case of a robot
vehicle is the real sky blue. The sky contains vector pointers; and
would be more efficient on a virtual memory machine that didn't
allocate unused pages of its address space. Whereas most computers
have more memory containers than address space; computer graphics
and vision might be easier to program in a memory with more address
space than physical space; i.e. an almost empty virtual memory.
The first part of the INTREE routine finds the surrounder of
a given polygon by scanning the SKY due east from the uppermost left
pixel of the given polygon. The SON of a polygon is always its
uppermost left vector. After INTREE, the INSKY routine places
pointers to the vertical vectors of the given polygon into the sky
array.
The second part of the INTREE routine checks for and fixes
up the case where the new polygon captures a polygon that is already
enclaved. This only happens when two or more levels of the image
have blobs that have holes. The next paragraph expalains the arcane
details of fixing up the tree links of multi level hole polygons and
the box following that is a quotation from the appendix of Krakauer
thesis [3] describing his nesting algorithm.
NESTING.
Let the given polygon be named Poly; and let the surrounder
of Poly be called Exopoly; and assume that Exopoly surrounds several
enclaved polygons called "endo's", which are already in the nested
polygon tree. Also, there are two kinds of temporary lists named the
PLIST and the NLIST. There is one PLIST which is initially a list of
all the ENDO polygons on Exopoly's ENDO ring. Each endo in turn has
an NLIST which is initially empty. The subroutine INTREE re-scans
the sky array for the polygon due east of the uppermost left vector
of each endo polygon on the PLIST, (Exopoly's ENDO ring). On such
re-scanning, (on behalf of say an Endo1), there are four cases:
1. No change; the scan returns Exopoly;
which is Endo1's original EXO.
2. Poly captures Endo1; the scan returns Poly indicating
that endo1 has been captured by Poly.
3. My brothers fate; the scan hits an endo2 which
is not on the PLIST; which means that endo2's EXO is valid
and is the valid EXO of endo1.
4. My fate delayed; the scan hits an endo2 which is still
on the PLIST; which means that endo2's EXO is not yet
valid but when discovered it will also be Endo1's EXO;
so Endo1 is CONS'ed into Endo2's NLIST.
When an endo polygon's EXO has been re-discovered, then all the
polygons on that endo's NLIST are also placed into the polygon tree
at that place. All of this link crunching machinery takes half a page
of code and is not frequently executed.
CONTOUR SEGMENTION
In CRE the term "smoothing" refers more to the problem of
breaking a manifold (polygon) into functions (arcs), rather than to
the problem of fitting functions to measured data. The smoothing
step, converts the polygons of vertical and horizontal vectors into
polygons of arcs. For the present the term "arc" means "linear arc"
which is a line segment. Fancier arcs: circular and cubic spline
were implemented and thrown out mostly because they were of no use
to higher processes such as the polygon compare which would break
the fancier arcs back down into linear vectors for computing areas,
inertia tensors or mere display buffers.
Smoothing is applied to each polygon of a level. To start
the smoothing, a ring of two arcs is formed (a bi-gon) with one arc
at the uppermost left and the other at the lowermost right of the
given vector polygon. Next a recursive make arc operation, MKARC, is
is appled to the two initial arcs. Since the arc given to MKARC is
in a one to one correspondece with a doubly linked list of vectors;
MKARC checks to see whether each point on the list of vectors is
close enough to the approximating arc. MKARC returns the given arc
as good enough when all the sub vectors fall within a given width;
otherwise MKARC splits the arc in two and places a new arc vertex on
the vector vertex that was furthest away from the original arc.
The two large images in figure-7, illustrate a polygon
smoothed with arc width tolerances set at two different widths in
order to show one recursion of MKARC. The eight smaller images
illustrate the results of setting the arc width tolerance over a
range of values. Because of the dekinking mentioned earlier the arc
width tolerance can be equal to or less than 1.0 pixels and still
expect a substantial reduction in the number of vectors it takes to
describe a contour polygon.
A final important smoothing detail is that the arc width
tolerance is actually taken as a function of the highest contrast
vector found along the arc; so that high contrast arcs are smoothed
with much smaller arc width tolerances than are low contrast arcs.
After smoothing, the contrast across each arc is computed and the
ring of arcs replaces the ring of vectors of the given polygon.
(Polygons that would be expressed as only two arcs are deleted).